// 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// dfs,递归
// 优化求xy和函数

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 56.77%
// 的用户
// 内存消耗：
// 6.7 MB
// , 在所有 C++ 提交中击败了
// 40.07%
// 的用户




class Solution {
public:
    int movingCount(int m, int n, int k) {
        // true代表未被走过
        vector<vector<bool>> vec(m,vector<bool>(n,true));
        int res=0;
        int x=0;
        int y=0;
        dfs(vec,k,0,0,res);
        return res;
    }

    void dfs(vector<vector<bool>>& vec,int& k,int x,int y,int& cnt){
        if(x>=vec.size() || y>=vec[0].size()){
            return;
        }
        else if(vec[x][y]==false){
            return;
        }
        else{
            if(is_small(x,y,k)){
                ++cnt;
                vec[x][y]=false;
                dfs(vec,k,x+1,y,cnt);
                dfs(vec,k,x-1,y,cnt);
                dfs(vec,k,x,y+1,cnt);
                dfs(vec,k,x,y-1,cnt);
            }
            else{
                vec[x][y]=false;
            }
        }
    }

    bool is_small(int x,int y,int& k){
        int sum =0;
        while(x!=0){
            sum = sum+x%10;
            x= x/10;
        }
        while(y!=0){
            sum = sum+y%10;
            y= y/10;
        }
        if(sum<=k){
            return true;
        }
        return false;
    }
};